﻿#include <iostream>
#include <queue>

using namespace std;

template<class T>
class StackByQueue
{
public:
    void push(T t);
    T pop();

private:
    queue<T> q1;
    queue<T> q2;
};

template<class T>
void StackByQueue<T>::push(T t)
{
    q1.push(t);
}

template<class T>
T StackByQueue<T>::pop()
{
    if (q1.empty()) return NULL;

    T top;
    while (q1.size() > 1)
    {
        top = q1.front();
        q1.pop();
        q2.push(top);
    }

    auto res = q1.front();
    q1.pop();
    while (!q2.empty())
    {
        top = q2.front();
        q2.pop();
        q1.push(top);
    }

    return res;
}

/**
 * 用队列模拟栈
 */
int main_UseQueueToMakeStack()
{
    int numbers[] = { 10,4,5,3,8,7,9,11,20,12,15 };
    int size = sizeof(numbers) / sizeof(int);
    StackByQueue<int> stack;
    for (int i = 0; i < size; i++)
    {
        stack.push(numbers[i]);
    }

    for (int i = 0; i < size; i++)
    {
        int p = stack.pop();
        printf("%d:%d\n", i, p);
    }

    return 0;
}